package 数据结构;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树(排序树)的遍历
 *
 * @author wxg
 */
public class BinTree {
    public static void main(String[] args) {
        BinTree binTree = new BinTree();
        binTree.put(8);
        binTree.put(5);
        binTree.put(4);
        binTree.put(7);
        binTree.put(6);
        binTree.put(11);
        binTree.put(10);
        binTree.put(12);
        /*
        *                        8
        *                      /   \
        *                     5    11
        *                    / \   / \
        *                   4   7 10 12
        *                      /
        *                     6
        * */
        System.out.println(binTree.preorder());
        System.out.println(binTree.midorder());
        System.out.println(binTree.postorder());
        /*
        * [8, 5, 4, 7, 6, 11, 10, 12]
          [4, 5, 6, 7, 8, 10, 11, 12]
          [4, 6, 7, 5, 10, 12, 11, 8]
        * */
    }

    private Node root;

    public void put(Integer ele) {
        Node newNode = new Node(null, ele, null);
        if (root == null) {
            root = newNode;
        } else {
            Node temp = root;
            Node curr = null;
            while (temp != null) {
                curr = temp;
                if (ele < temp.value)
                    temp = temp.left;
                else temp = temp.right;
            }
            if (ele < curr.value)
                curr.left = newNode;
            else curr.right = newNode;
        }
    }

    /**
     * 前序遍历
     *
     * @return
     */
    public List preorder() {
        List list = new ArrayList();
        preorder(list, root);
        return list;
    }

    /**
     * 中序遍历
     *
     * @return
     */
    public List midorder() {
        List list = new ArrayList();
        midorder(list, root);
        return list;
    }

    /**
     * 后续遍历
     *
     * @return
     */
    public List postorder() {
        List list = new ArrayList();
        postorder(list, root);
        return list;
    }

    private void preorder(List list, Node node) {
        if (node != null) {
            list.add(node.value);
            preorder(list, node.left);
            preorder(list, node.right);
        }
    }

    private void midorder(List list, Node node) {
        if (node != null) {
            midorder(list, node.left);
            list.add(node.value);
            midorder(list, node.right);
        }
    }

    private void postorder(List list, Node node) {
        if (node != null) {
            postorder(list, node.left);
            postorder(list, node.right);
            list.add(node.value);
        }
    }

    private class Node {
        private Integer value;
        private Node left;
        private Node right;

        Node(Node left, Integer value, Node right) {
            this.left = left;
            this.value = value;
            this.right = right;
        }
    }
}
